package com.LeeCode;

/**
 * 二叉搜索树的最近公共祖先
 */

public class Code235 {
    public static void main(String[] args) {
        Integer[] arr = {6, 2, 8, 0, 4, 7, 9, null, null, 3, 5};
        TreeNode root = Utils.buildTree(arr);
        TreeNode p = root.left;
        TreeNode q = root.right;
        System.out.println(new Code235().lowestCommonAncestor(root, p, q).val);
    }

    private TreeNode ans;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;

        boolean left = dfs(root.left, p, q);
        boolean right = dfs(root.right, p, q);

        boolean flag = (root == p || root == q);

        // 如果当前节点是 LCA，记录它
        if ((left && right) || (flag && (left || right))) {
            ans = root;
        }

        // 返回：当前子树是否包含 p 或 q
        return left || right || flag;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        int x = root.val;
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
